// 二分查找 - 利用数组的 二段性 解决问题，每次可以舍弃一段数据
// 经典在 有序数组中 找一个数/找一个数的插入位置 的问题，都可以使用二分查找
// 二分查找通常需要借助一个 target 值来将数组分成两段，以便于每次舍去一部分

// target 的值在简单题目中会直接给出，复杂一点的题目不会直接给出，需要自己找一个值
// 找这个值的方法就需要能把数组分成两段

// 例题 8：
// 某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
//
//        示例 1：
//
//        输入：records = [0,1,2,3,5]
//        输出：4
//        示例 2：
//
//        输入：records = [0, 1, 2, 3, 4, 5, 6, 8]
//        输出：7
//
//
//        提示：
//
//        1 <= records.length <= 10000

// 解题思路：

// 本地有多种解法可以求解：可以用哈希表统计，可以遍历一遍，也可以使用位运算抑或，还可以使用高斯求和的方法，时间复杂度均为 O(n)
// 同时本题也命中了 二段性 的特点，因此可以用二分查找求解，二分查找的时间复杂度为 O(log n)
// 可以根据下标和元素的对应关系将数据划分成两段：
// 第一段：index = records[index]
// 第二段：index < records[index]

// 左中点：mid = left + (right - left) / 2
// x > target: left = mid + 1
// x <= target: right = mid;


public class TakeAttendance {
    public int takeAttendance(int[] records) {
        int n = records.length;
        int left = 0; int right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(records[mid] <= mid) left = mid + 1;
            else right = mid;
        }
        return records[left] == left ? left + 1 : left;
    }
}
